Exercici 15 (Tasca 2).
(regular languages,
first half,
hard exercise)
La primera meitat d’un regular és regular
Donat un llenguatge L, definim \mathtt{PrimeraMeitat}(L) com el conjunt de mots que constitueixen la primera meitat de mots de mida parella a L, és a dir, \mathtt{PrimeraMeitat}(L)= \{x \mid \exists y \, (|x|=|y| \, \wedge \, xy \in L)\}. Demostreu que si L és regular, aleshores \mathtt{PrimeraMeitat}(L) és regular.